package com.algorithm.liyc.echa;

import com.algorithm.liyc.entity.Node;
import com.algorithm.liyc.entity.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 104.二叉树的最大深度
 * 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * ● 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
 * ● 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
 * 而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
 *
 * @author Liyc
 * @date 2023/12/29 14:09
 **/

public class Solution7 {
    /**
     * 递归法
     * 按深度查询
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftMax = maxDepth1(root.left);
        int rightMax = maxDepth1(root.right);
        return Math.max(leftMax, rightMax) + 1;
    }

    /**
     * 递归法
     * 按高度查询
     * @param root
     * @return
     */
    public int maxNum = 0;
    public int maxDepth2(TreeNode root) {
        int tmp = 0;
        getMaxDe(root, tmp);
        return maxNum;
    }
    public void getMaxDe(TreeNode root, int tmp) {
        if (root == null) {
            return;
        }
        tmp++;
        maxNum = maxNum<tmp ? tmp : maxNum;
        getMaxDe(root.left, tmp);
        getMaxDe(root.right, tmp);
        tmp--;
    }

    /**
     * 迭代法，使用层序遍历
     * @param root
     * @return
     */
    public int maxDepth3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
        int maxDepth = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            maxDepth++;
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.poll();
                if (treeNode.left != null) {
                    deque.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    deque.offer(treeNode.right);
                }
            }
        }
        return maxDepth;
    }

    /**
     * 559.n叉树的最大深度
     * 递归法
     * @param root
     * @return
     */
    public int maxDepthN1(Node root) {
        if (root == null) {
            return 0;
        }
        int maxNumN = 0;
        if (root.children != null) {
            for (int i = 0; i < root.children.size(); i++) {
                maxNumN = Math.max(maxNumN, maxDepthN1(root.children.get(i)));
            }
        }
        return maxNumN + 1;
    }

    /**
     * 559.n叉树的最大深度
     * 迭代法，层序遍历
     * @param root
     * @return
     */
    public int maxDepthN2(Node root) {
        if (root == null) {
            return 0;
        }
        Deque<Node> deque = new LinkedList<>();
        deque.offer(root);
        int maxNumN = 0;
        while (!deque.isEmpty()) {
            int len = deque.size();
            maxNumN++;
            while (len > 0) {
                Node node = deque.poll();
                for (int i = 0; i < node.children.size(); i++) {
                    if (node.children.get(i) != null) {
                        deque.offer(node.children.get(i));
                    }
                }
                len--;
            }

        }
        return maxNumN;
    }
}
